#include <stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int datatype;
typedef struct list {
	datatype data;
	struct list* next;
}node;
node* reverse(node* head) {
	if (head == NULL) {
		return head;
	}
	node* n1, * n2, * n3;
	n1 = NULL;
	n2 = head;
	n3 = n2->next;
	while (n2) {
		n2->next = n1;
		n1 = n2;
		n2 = n3;
		if (n3)
			n3 = n3->next;
	}
	return n1;
}
node* buynode(datatype x) {
	node* newnode = (node*)malloc(sizeof(node));
	if (newnode == NULL) {
		printf("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void pushback(node** head, datatype x) {
	assert(head);
	node* newnode = buynode(x);
	if (*head == NULL) {
		*head = newnode;
	}
	else {
		node* tail = *head;
		while (tail->next) {
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void destroy(node** head) {
	assert(head && *head);
	node* pcur = *head;
	while (pcur) {
		node* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	head = NULL;
}
void print(node* head) {
	node* pcur = head;
	while (pcur) {
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

int main() {
	node* list = NULL;
	pushback(&list, 1);
	pushback(&list, 2);
	pushback(&list, 3);
	pushback(&list, 4);
	print(list);
	list=reverse(list);
	print(list);
	destroy(&list);
	return 0;
}
